/**
 * @author Liwen CHU
 * All code in this file is an answer to prior examination for WorksApplication internship. * 
 */

package my.collections;

import java.util.ArrayList;
import java.util.EmptyStackException;

public class StackForPriorExaminationImpl<E extends Comparable<E>> implements
		IStackForPriorExamination<E> {
	/**
	 * Stack size
	 * Use a variable to indicate the size of stack instead of calling .size() method of ArrayList
	 */
	private int _size = 0;
	
	/**
	 * Use an ArrayList to store elements
	 */
	private ArrayList<E> _stack = new ArrayList<E>();

	//Default constructor
	public StackForPriorExaminationImpl(){		
	}

	/**
	 * Append element to the end of the list
	 * Increase stack size
	 */
	@Override
	public void push(E e) {
		if(e.equals(null)){
			throw new NullPointerException();
		}
		_stack.add(e);
		++_size;
	}

	/**
	 * Remove and return element at the end of the list
	 * Decrease stack size 
	 */
	@Override
	public synchronized E pop() {
		if(_size <= 0){
			throw new EmptyStackException();
		}
		
		--_size;
		return _stack.remove(_size);
	}
	
	/**
	 * Return maximum object in the stack
	 * Considering any element in the stack could be modified at any time outside the class,
	 * so any algorithm based on index structures which can be constructed when pushing elements 
	 * into stack would fail if any element is modified outside the stack class. 
	 * So the O(n) algorithms is employed to find the maximum 
	 */
	@Override
	public E peekMaximum() {
		if(_size <= 0){
			throw new EmptyStackException();
		}		
		
		E max = _stack.get(0);
		int size = _size;
		for(int i = 1; i < size; ++i){
			if(max.compareTo(_stack.get(i))< 0){
				max = _stack.get(i);
			}
		}				
		return max;
	}
	
	/**
	 * A quick-sort derived algorithms is used to find the median object and the 
	 * algorithms is implemented none-recursively to improve performance and on 
	 * average the time complexity is O(n)
	 */
	@SuppressWarnings("unchecked")
	@Override
	public E peekMedian() {
		if(_size <= 0){
			throw new EmptyStackException();
		}
		
		//Make a shallow copy of current stack as the algorithm requires modification to 
		//the stack to find median object
		ArrayList<E> lst = (ArrayList<E>) _stack.clone();
		int low = 0, high = _size - 1;
		int median = _size / 2;
		int mid, ll, hh;
		
		for(;;){
			//If only one element in the range 
			if(high <= low){
				return lst.get(median);
			}
			
			//If only two elements in the range
			if(high == low + 1){
				if(lst.get(low).compareTo(lst.get(high)) > 0){
					Swap(lst, low, high);
				}
				return lst.get(median);
			}
			
			//Choose a pivot element
			mid = (low + high) / 2;
			if(lst.get(mid).compareTo(lst.get(high)) > 0){
				Swap(lst, mid, high);
			}			
			if(lst.get(low).compareTo(lst.get(high)) > 0){
				Swap(lst, low, high);
			}			
			if(lst.get(mid).compareTo(lst.get(low)) > 0){
				Swap(lst, mid, low);
			}			
			Swap(lst, mid, low+1);
			
			//Partitioning the array and elements less than the pivot are placed
			//in range of [low..hh]
			ll = low + 1;
			hh = high;
			for(;;){
				while((ll < hh) && (lst.get(low).compareTo(lst.get(ll)) >= 0)){
					++ll;
				}
				
				while(lst.get(hh).compareTo(lst.get(low)) > 0){
					--hh;
				}
				
				if(hh <= ll){
					break;
				}
				
				Swap(lst, ll, hh);
			}			
			Swap(lst, low, hh);
			
			//Update the target range that contains the median object
			if(hh < median){
				low = ll;							
			}
			else if (hh > median){
				high = hh - 1;
			}
			else{
				return lst.get(hh);
			}
		}
	}
	
	/**
	 * Helper function to swap two elements in an array
	 * @param arr
	 * @param i
	 * @param j
	 */
	private final void Swap(ArrayList<E> arr, int i, int j){
		E tmp = arr.get(i);
		arr.set(i, arr.get(j));
		arr.set(j, tmp);
	}

	/**
	 * Return minimum object in the stack
	 * Considering any element in the stack could be modified at any time outside the class,
	 * so any algorithm based on index structures which can be constructed when pushing elements 
	 * into stack would fail if any element is modified outside the stack class. 
	 * As a result the O(n) algorithms is employed to find the minimum 
	 */	
	@Override
	public E peekMinimum() {
		if(_stack.isEmpty()){
			throw new EmptyStackException();
		}
		
		int size = _size;
		
		E min = _stack.get(0);
		for(int i = 1; i < size; ++i){
			if(min.compareTo(_stack.get(i)) > 0){
				min = _stack.get(i);
			}
		}
		
		return min;
	}

	/**
	 * Return the size of the stack
	 */
	@Override
	public int size() {
		return _size;
	}
}
